home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / gnulib / gnucdiff / diff3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-12-16  |  46.5 KB  |  1,591 lines
  1. /* Three-way file comparison program (diff3) for Project GNU
  2.    Copyright (C) 1988 Free Software Foundation, Inc.
  3.  
  4.                NO WARRANTY
  5.  
  6.   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  7. NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  8. WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  9. RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  10. WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  11. BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  12. FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  13. AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  14. DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  15. CORRECTION.
  16.  
  17.  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  18. STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  19. WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  20. LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  21. OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  22. USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  23. DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  24. A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  25. PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  26. DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  27.  
  28.         GENERAL PUBLIC LICENSE TO COPY
  29.  
  30.   1. You may copy and distribute verbatim copies of this source file
  31. as you receive it, in any medium, provided that you conspicuously
  32. and appropriately publish on each copy a valid copyright notice
  33. "Copyright (C) 1988 Free Software Foundation, Inc.", and include
  34. following the copyright notice a verbatim copy of the above disclaimer
  35. of warranty and of this License.
  36.  
  37.   2. You may modify your copy or copies of this source file or
  38. any portion of it, and copy and distribute such modifications under
  39. the terms of Paragraph 1 above, provided that you also do the following:
  40.  
  41.     a) cause the modified files to carry prominent notices stating
  42.     that you changed the files and the date of any change; and
  43.  
  44.     b) cause the whole of any work that you distribute or publish,
  45.     that in whole or in part contains or is a derivative of this
  46.     program or any part thereof, to be licensed at no charge to all
  47.     third parties on terms identical to those contained in this
  48.     License Agreement (except that you may choose to grant more extensive
  49.     warranty protection to some or all third parties, at your option).
  50.  
  51.     c) You may charge a distribution fee for the physical act of
  52.     transferring a copy, and you may at your option offer warranty
  53.     protection in exchange for a fee.
  54.  
  55. Mere aggregation of another unrelated program with this program (or its
  56. derivative) on a volume of a storage or distribution medium does not bring
  57. the other program under the scope of these terms.
  58.  
  59.   3. You may copy and distribute this program (or a portion or derivative
  60. of it, under Paragraph 2) in object code or executable form under the terms
  61. of Paragraphs 1 and 2 above provided that you also do one of the following:
  62.  
  63.     a) accompany it with the complete corresponding machine-readable
  64.     source code, which must be distributed under the terms of
  65.     Paragraphs 1 and 2 above; or,
  66.  
  67.     b) accompany it with a written offer, valid for at least three
  68.     years, to give any third party free (except for a nominal
  69.     shipping charge) a complete machine-readable copy of the
  70.     corresponding source code, to be distributed under the terms of
  71.     Paragraphs 1 and 2 above; or,
  72.  
  73.     c) accompany it with the information you received as to where the
  74.     corresponding source code may be obtained.  (This alternative is
  75.     allowed only for noncommercial distribution and only if you
  76.     received the program in object code or executable form alone.)
  77.  
  78. For an executable file, complete source code means all the source code for
  79. all modules it contains; but, as a special exception, it need not include
  80. source code for modules which are standard libraries that accompany the
  81. operating system on which the executable file runs.
  82.  
  83.   4. You may not copy, sublicense, distribute or transfer this program
  84. except as expressly provided under this License Agreement.  Any attempt
  85. otherwise to copy, sublicense, distribute or transfer this program is void and
  86. your rights to use the program under this License agreement shall be
  87. automatically terminated.  However, parties who have received computer
  88. software programs from you with this License Agreement will not have
  89. their licenses terminated so long as such parties remain in full compliance.
  90.  
  91.   5. If you wish to incorporate parts of this program into other free
  92. programs whose distribution conditions are different, write to the Free
  93. Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  94. worked out a simple rule that can be stated here, but we will often permit
  95. this.  We will be guided by the two goals of preserving the free status of
  96. all derivatives of our free software and of promoting the sharing and reuse of
  97. software.
  98.  
  99.  In other words, you are welcome to use, share and improve this program.
  100.  You are forbidden to forbid anyone else to use, share and improve
  101.  what you give them.   Help stamp out software-hoarding!  */
  102.  
  103. /* Written by Randy Smith */
  104.  
  105. /* 
  106.  * Include files.
  107.  */
  108. #include "diff.h"
  109.  
  110. /*
  111.  * Internal data structures and macros for the diff3 program; includes
  112.  * data structures for both diff3 diffs and normal diffs.
  113.  */
  114.  
  115. /*
  116.  * Different files within a diff
  117.  */
  118. #define    FILE0    0
  119. #define    FILE1    1
  120. #define    FILE2    2
  121.  
  122. /*
  123.  * Three way diffs are build out of two two-way diffs; the file which
  124.  * the two two-way diffs share is:
  125.  */
  126. #define    FILEC    FILE0
  127.  
  128. /* The ranges are indexed by */
  129. #define    START    0
  130. #define    END    1
  131.  
  132. enum diff_type {
  133.   ERROR,            /* Should not be used */
  134.   ADD,                /* Two way diff add */
  135.   CHANGE,            /* Two way diff change */
  136.   DELETE,            /* Two way diff delete */
  137.   DIFF_ALL,            /* All three are different */
  138.   DIFF_1ST,            /* Only the first is different */
  139.   DIFF_2ND,            /* Only the second */
  140.   DIFF_3RD            /* Only the third */
  141. };
  142.  
  143. /* Two-way diff */
  144. struct diff_block {
  145.   int ranges[2][2];            /* Ranges are inclusive */
  146.   char **lines[2];        /* The actual lines (may contain nulls) */
  147.   int *lengths[2];        /* The lengths of the lines (since nulls) */
  148.   struct diff_block *next;
  149. };
  150.  
  151. /* Three-way diff */
  152.  
  153. struct diff3_block {
  154.   enum diff_type correspond;    /* Type of diff */
  155.   int ranges[3][2];            /* Ranges are inclusive */
  156.   char **lines[3];        /* The actual lines (may contain nulls) */
  157.   int *lengths[3];        /* The lengths of the lines (since nulls) */
  158.   struct diff3_block *next;
  159. };
  160.  
  161. /*
  162.  * Access the ranges on a diff block.
  163.  */
  164. #define    D_LOWLINE(diff, filenum)    \
  165.   ((diff)->ranges[filenum][START])
  166. #define    D_HIGHLINE(diff, filenum)    \
  167.   ((diff)->ranges[filenum][END])
  168. #define    D_NUMLINES(diff, filenum)    \
  169.   (D_HIGHLINE((diff), (filenum)) - D_LOWLINE((diff), (filenum)) + 1)
  170.  
  171. /*
  172.  * Access the line numbers in a file in a diff by absolute line number
  173.  * (ie. line number within the original file).  Note that these are
  174.  * lvalues and can be used for assignment.
  175.  */
  176. #define    D_LINENUM(diff, filenum, linenum)    \
  177.   (*((diff)->lines[filenum] + linenum - D_LOWLINE((diff), (filenum))))
  178. #define    D_LINELEN(diff, filenum, linenum)    \
  179.   (*((diff)->lengths[filenum] + linenum - D_LOWLINE((diff), (filenum))))
  180.  
  181. /*
  182.  * Access the line numbers in a file in a diff by relative line
  183.  * numbers (ie. line number within the diff itself).  Note that these
  184.  * are lvalues and can be used for assignment.
  185.  */
  186. #define    D_RELNUM(diff, filenum, linenum)    \
  187.   (*((diff)->lines[filenum] + linenum))
  188. #define    D_RELLEN(diff, filenum, linenum)    \
  189.   (*((diff)->lengths[filenum] + linenum))
  190.  
  191. /*
  192.  * And get at them directly, when that should be necessary.
  193.  */
  194. #define    D_LINEARRAY(diff, filenum)    \
  195.   ((diff)->lines[filenum])
  196. #define    D_LENARRAY(diff, filenum)    \
  197.   ((diff)->lengths[filenum])
  198.  
  199. /*
  200.  * Next block.
  201.  */
  202. #define    D_NEXT(diff)    ((diff)->next)
  203.  
  204. /*
  205.  * Access the type of a diff3 block.
  206.  */
  207. #define    D3_TYPE(diff)    ((diff)->correspond)
  208.  
  209. /*
  210.  * Line mappings based on diffs.  The first maps off the top of the
  211.  * diff, the second off of the bottom.
  212.  */
  213. #define    D_HIGH_MAPLINE(diff, fromfile, tofile, lineno)    \
  214.   ((lineno)                        \
  215.    - D_HIGHLINE ((diff), (fromfile))            \
  216.    + D_HIGHLINE ((diff), (tofile)))
  217.  
  218. #define    D_LOW_MAPLINE(diff, fromfile, tofile, lineno)    \
  219.   ((lineno)                        \
  220.    - D_LOWLINE ((diff), (fromfile))            \
  221.    + D_LOWLINE ((diff), (tofile)))
  222.  
  223. /*
  224.  * General memory allocation function.
  225.  */
  226. #define    ALLOCATE(number, type)    \
  227.   (type *) xmalloc ((number) * sizeof (type))
  228.  
  229. /*
  230.  * Options variables for flags set on command line.
  231.  *
  232.  * EDSCRIPT: Write out an ed script instead of the standard diff3 format.
  233.  *
  234.  * FLAGGING: Indicates that in the case of overlapping diffs (type
  235.  * DIFF_ALL), the lines which would normally be deleted from file 1
  236.  * should be preserved with a special flagging mechanism.
  237.  *
  238.  * DONT_WRITE_OVERLAP: 1 if information for overlapping diffs should
  239.  * not be output.
  240.  *
  241.  * DONT_WRITE_SIMPLE: 1 if information for non-overlapping diffs
  242.  * should not be output. 
  243.  *
  244.  * FINALWRITE: 1 if a :wq should be included at the end of the script
  245.  * to write out the file being editted.
  246.  */
  247. int edscript;
  248. int flagging;
  249. int dont_write_overlap;
  250. int dont_write_simple;
  251. int finalwrite;
  252. void fatal();
  253.  
  254. extern int optind;
  255.  
  256. char *argv0;
  257.  
  258. /*
  259.  * Forward function declarations.
  260.  */
  261. struct diff_block *process_diff ();
  262. struct diff3_block *make_3way_diff ();
  263. void output_diff3 ();
  264. void output_diff3_edscript ();
  265. void usage ();
  266.  
  267. struct diff3_block *using_to_diff3_block ();
  268. int copy_stringlist ();
  269. struct diff3_block *create_diff3_block ();
  270. int compare_line_list ();
  271.  
  272. int read_diff ();
  273. enum diff_type process_diff_control ();
  274. char *scan_diff_line ();
  275.  
  276. struct diff3_block *reverse_diff3_blocklist ();
  277.  
  278. void *xmalloc ();
  279. void *xrealloc ();
  280.  
  281. /*
  282.  * No options take arguments.  "i" is my own addition; it stands for
  283.  * "include write command", to emulate system V behaivior.
  284.  */
  285. #define    ARGSTRING    "eix3EX"
  286.  
  287. /* char diff_program[] = DIFF_PROGRAM; */
  288. char diff_program[] = "diff";
  289.  
  290. /*
  291.  * Main program.  Calls diff twice on two pairs of input files,
  292.  * combines the two diffs, and outputs them.
  293.  */
  294.  
  295. void
  296. main(argc, argv)
  297. int argc;
  298. char **argv;
  299. {
  300.   int c;
  301.   int mapping [3];
  302.   int shiftmap;
  303.   int incompat;
  304.   extern char *basename();
  305.   struct diff_block *thread1, *thread2;
  306.   struct diff3_block *diff;
  307.  
  308.   edscript = flagging = dont_write_overlap
  309.     = dont_write_simple = finalwrite = 0;
  310.   incompat = shiftmap = 0;
  311.  
  312.   argv0 = basename(argv[0]);
  313.   
  314.   while ((c = getopt (argc, argv, ARGSTRING)) != EOF)
  315.     {
  316.       edscript = 1;
  317.       switch (c)
  318.     {
  319.     case 'x':
  320.       dont_write_simple = 1;
  321.       incompat++;
  322.       break;
  323.     case '3':
  324.       dont_write_overlap = 1;
  325.       incompat++;
  326.       break;
  327.     case 'i':
  328.       finalwrite = 1;
  329.       incompat++;
  330.       break;
  331.     case 'X':
  332.       dont_write_simple = 1;
  333.       /* Falls through */
  334.     case 'E':
  335.       flagging = 1;
  336.       /* Falls through */
  337.     case 'e':
  338.       incompat++;
  339.       break;
  340.     case '?':
  341.     default:
  342.       usage ();
  343.       /* NOTREACHED */
  344.     }
  345.     }
  346.  
  347.   if (incompat > 1)        /* Make sure you only have one of a */
  348.                 /* set of arguments */
  349.     usage ();
  350.   
  351.   if (argc - optind != 3)
  352.     usage ();
  353.  
  354.   if (*argv[optind] == '-' && *(argv[optind] + 1) == '\0')
  355.     {
  356.       /* Sigh.  We've got standard input as the first arg. We can't */
  357.       /* call diff twice on stdin */
  358.       mapping [0] = 1;
  359.       mapping [1] = 2;
  360.       mapping [2] = 0;
  361.       shiftmap = 1;
  362.     }
  363.   else
  364.     {
  365.       /* Normal, what you'd expect */
  366.       mapping [0] = 0;
  367.       mapping [1] = 1;
  368.       mapping [2] = 2;
  369.       shiftmap = 0;
  370.     }
  371.  
  372.   if (shiftmap)
  373.     {
  374.       thread1 = process_diff (argv[optind + 2], argv[optind]);
  375.       thread2 = process_diff (argv[optind + 2], argv[optind + 1]);
  376.     }
  377.   else
  378.     {
  379.       thread1 = process_diff (argv[optind], argv[optind + 1]);
  380.       thread2 = process_diff (argv[optind], argv[optind + 2]);
  381.     }
  382.   diff = make_3way_diff (thread1, thread2);
  383.   if (edscript)
  384.     output_diff3_edscript (stdout, diff, mapping, argv[optind],
  385.                argv[optind + 1], argv[optind + 2]);
  386.   else
  387.     output_diff3 (stdout, diff, mapping);
  388.  
  389.   exit (0);
  390. }
  391.       
  392. /*
  393.  * Explain, patiently and kindly, how to use this program.  Then exit.
  394.  */
  395. void
  396. usage ()
  397. {
  398.   fprintf (stderr, "Usage:\t%s [ -exEX3 ] [ -i ] file1 file2 file3\n",
  399.        argv0);
  400.   fprintf (stderr, "\tOnly one of [exEX3] allowed\n");
  401.   exit (1);
  402. }
  403.  
  404. /*
  405.  * Routines that combine the two diffs together into one.  The
  406.  * algorithm used follows:
  407.  *
  408.  *   File0 is shared in common between the two diffs.
  409.  *   Diff01 is the diff between 0 and 1.
  410.  *   Diff02 is the diff between 0 and 2.
  411.  *
  412.  *     1) Find the range for the first block in File0.
  413.  *          a) Take the lowest of the two ranges (in File0) in the two
  414.  *             current blocks (one from each diff) as being the low
  415.  *             water mark.  Assign the upper end of this block as
  416.  *             being the high water mark and move the current block up
  417.  *             one.  Mark the block just moved over as to be used.
  418.  *        b) Check the next block in the diff that the high water
  419.  *             mark is *not* from.  
  420.  *           
  421.  *           *If* the high water mark is above
  422.  *             the low end of the range in that block, 
  423.  * 
  424.  *               mark that block as to be used and move the current
  425.  *                 block up.  Set the high water mark to the max of
  426.  *                 the high end of this block and the current.  Repeat b.
  427.  * 
  428.  *       2) Find the corresponding ranges in Files1 (from the blocks
  429.  *          in diff01; line per line outside of diffs) and in File2.
  430.  *          Create a diff3_block, reserving space as indicated by the ranges.
  431.  *        
  432.  *     3) Copy all of the pointers for file0 in.  At least for now,
  433.  *          do bcmp's between correspponding strings in the two diffs.
  434.  *        
  435.  *     4) Copy all of the pointers for file1 and 2 in.  Get what you
  436.  *          need from file0 (when there isn't a diff block, it's
  437.  *          identical to file0 within the range between diff blocks).
  438.  *        
  439.  *     5) If the diff blocks you used came from only one of the two
  440.  *         strings of diffs, then that file (ie. the one other than
  441.  *         file 0 in that diff) is the odd person out.  If you used
  442.  *         diff blocks from both sets, check to see if files 1 and 2 match:
  443.  *        
  444.  *            Same number of lines?  If so, do a set of bcmps (if a
  445.  *          bcmp matches; copy the pointer over; it'll be easier later
  446.  *          if you have to do any compares).  If they match, 1 & 2 are
  447.  *          the same.  If not, all three different.
  448.  * 
  449.  *   Then you do it again, until you run out of blocks. 
  450.  * 
  451.  */
  452.  
  453. /* 
  454.  * This routine makes a three way diff (chain of diff3_block's) from two
  455.  * two way diffs (chains of diff_block's).  It is assumed that each of
  456.  * the two diffs passed are off of the same file (ie. that each of the
  457.  * diffs were made "from" the same file).  The three way diff pointer
  458.  * returned will have numbering 0--the common file, 1--the other file
  459.  * in diff1, and 2--the other file in diff2.
  460.  */
  461. struct diff3_block *
  462. make_3way_diff (thread1, thread2)
  463. struct diff_block *thread1, *thread2;
  464. {
  465. /*
  466.  * This routine works on the two diffs passed to it as threads.
  467.  * Thread number 0 is diff1, thread number 1 is diff2.  The USING
  468.  * array is set to the base of the list of blocks to be used to
  469.  * construct each block of the three way diff; if no blocks from a
  470.  * particular thread are to be used, that element of the using array
  471.  * is set to 0.  The elements LAST_USING array are set to the last
  472.  * elements on each of the using lists.
  473.  *
  474.  * The HIGH_WATER_MARK is set to the highest line number in File 0
  475.  * described in any of the diffs in either of the USING lists.  The
  476.  * HIGH_WATER_THREAD names the thread.  Similarly the BASE_WATER_MARK
  477.  * and BASE_WATER_THREAD describe the lowest line number in File 0
  478.  * described in any of the diffs in either of the USING lists.  The
  479.  * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was
  480.  * taken. 
  481.  *
  482.  * The HIGH_WATER_DIFF should always be equal to LAST_USING
  483.  * [HIGH_WATER_THREAD].  The OTHER_DIFF is the next diff to check for
  484.  * higher water, and should always be equal to
  485.  * CURRENT[HIGH_WATER_THREAD ^ 0x1].  The OTHER_THREAD is the thread
  486.  * in which the OTHER_DIFF is, and hence should always be equal to
  487.  * HIGH_WATER_THREAD ^ 0x1.
  488.  *
  489.  * The variable LAST_DIFF is kept set to the last diff block produced
  490.  * by this routine, for line correspondence purposes between that diff
  491.  * and the one currently being worked on.  It is initialized to
  492.  * ZERO_DIFF before any blocks have been created.
  493.  */
  494.  
  495.   struct diff_block
  496.     *using[2],
  497.     *last_using[2],
  498.     *current[2];
  499.  
  500.   int
  501.     high_water_mark,
  502.     base_water_mark;
  503.  
  504.   int
  505.     high_water_thread,
  506.     base_water_thread,
  507.     other_thread;
  508.  
  509.   struct diff_block
  510.     *high_water_diff,
  511.     *other_diff;
  512.  
  513.   struct diff3_block
  514.     *result,
  515.     *tmpblock,
  516.     *result_last,
  517.     *last_diff;
  518.  
  519.   static struct diff3_block zero_diff = {
  520.       ERROR,
  521.       { {0, 0}, {0, 0}, {0, 0} },
  522.       { (char **) 0, (char **) 0, (char **) 0 },
  523.       { (int *) 0, (int *) 0, (int *) 0 },
  524.       (struct diff3_block *) 0
  525.       };
  526.  
  527.   /* Initialization */
  528.   result = result_last = (struct diff3_block *) 0;
  529.   current[0] = thread1; current[1] = thread2;
  530.   last_diff = &zero_diff;
  531.  
  532.   /* Sniff up the threads until we reach the end */
  533.  
  534.   while (current[0] || current[1])
  535.     {
  536.       using[0] = using[1] = last_using[0] = last_using[1] =
  537.     (struct diff_block *) 0;
  538.  
  539.       /* Setup low and high water threads, diffs, and marks */
  540.       if (!current[0])
  541.     base_water_thread = 1;
  542.       else if (!current[1])
  543.     base_water_thread = 0;
  544.       else
  545.     base_water_thread =
  546.       (D_LOWLINE (current[0], FILE0)
  547.        > D_LOWLINE (current[1], FILE0));
  548.       high_water_thread = base_water_thread;
  549.       
  550.       high_water_diff = current[high_water_thread];
  551.     
  552.       /* low and high waters start off same diff */
  553.       base_water_mark = D_LOWLINE (high_water_diff, FILE0);
  554.  
  555.       high_water_mark = D_HIGHLINE (high_water_diff, FILE0);
  556.  
  557.       /* Make the diff you just got info from into the using class */
  558.       using[high_water_thread]
  559.     = last_using[high_water_thread]
  560.     = high_water_diff;
  561.       current[high_water_thread] = high_water_diff->next;
  562.       last_using[high_water_thread]->next
  563.     = (struct diff_block *) 0;
  564.  
  565.       /* And mark the other diff */
  566.       other_thread = high_water_thread ^ 0x1;
  567.       other_diff = current[other_thread];
  568.  
  569.       /* Shuffle up the ladder, checking the other diff to see if it
  570.          needs to be incorporated */
  571.       while (other_diff
  572.          && D_LOWLINE (other_diff, FILE0) <= high_water_mark + 1)
  573.     {
  574.  
  575.       /* Incorporate this diff into the using list.  Note that
  576.          this doesn't take it off the current list */
  577.       if (using[other_thread])
  578.         last_using[other_thread]->next = other_diff;
  579.       else
  580.         using[other_thread] = other_diff;
  581.       last_using[other_thread] = other_diff;
  582.  
  583.       /* Take it off the current list.  Note that this following
  584.          code assumes that other_diff enters it equal to
  585.          current[high_water_thread ^ 0x1] */
  586.       current[other_thread]
  587.         = current[other_thread]->next;
  588.       other_diff->next
  589.         = (struct diff_block *) 0;
  590.  
  591.       /* Set the high_water stuff
  592.          If this comparison is equal, then this is the last pass
  593.          through this loop; since diff blocks within a given
  594.          thread cannot overlap, the high_water_mark will be
  595.          *below* the range_start of either of the next diffs. */
  596.  
  597.       if (high_water_mark < D_HIGHLINE (other_diff, FILE0))
  598.         {
  599.           high_water_thread ^= 1;
  600.           high_water_diff = other_diff;
  601.           high_water_mark = D_HIGHLINE (other_diff, FILE0);
  602.         }
  603.  
  604.       /* Set the other diff */
  605.       other_thread = high_water_thread ^ 0x1;
  606.       other_diff = current[other_thread];
  607.     }
  608.  
  609.       /* The using lists contain a list of all of the blocks to be
  610.          included in this diff3_block.  Create it.  */
  611.  
  612.       tmpblock = using_to_diff3_block (using, last_using,
  613.                        base_water_thread, high_water_thread,
  614.                        last_diff);
  615.  
  616.       if (!tmpblock)
  617.     fatal ("internal: screwup in format of diff blocks");
  618.  
  619.       /* Put it on the list */
  620.       if (result)
  621.     result_last->next = tmpblock;
  622.       else
  623.     result = tmpblock;
  624.       result_last = tmpblock;
  625.  
  626.       /* Setup corresponding lines correctly */
  627.       last_diff = tmpblock;
  628.     }
  629.   return result;
  630. }
  631.  
  632. /*
  633.  * using_to_diff3_block:
  634.  *   This routine takes two lists of blocks (from two separate diff
  635.  * threads) and puts them together into one diff3 block.
  636.  * It then returns a pointer to this diff3 block or 0 for failure.
  637.  *
  638.  * All arguments besides using are for the convenience of the routine;
  639.  * they could be derived from the using array.
  640.  * LAST_USING is a pair of pointers to the last blocks in the using
  641.  * structure.
  642.  * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest
  643.  * and highest line numbers for File0.
  644.  * last_diff contains the last diff produced in the calling routine.
  645.  * This is used for lines mappings which would still be identical to
  646.  * the state that diff ended in.
  647.  *
  648.  * A distinction should be made in this routine between the two diffs
  649.  * that are part of a normal two diff block, and the three diffs that
  650.  * are part of a diff3_block.
  651.  */
  652. struct diff3_block *
  653. using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff)
  654. struct diff_block
  655.   *using[2],
  656.   *last_using[2];
  657. int low_thread, high_thread;
  658. struct diff3_block *last_diff;
  659. {
  660.   int lowc, highc, low1, high1, low2, high2;
  661.   struct diff3_block *result;
  662.   struct diff_block *ptr;
  663.   int i;
  664.   int current_line;
  665.   struct diff_block *last_block;
  666.   char **result_line_ptr;
  667.   int current0line;
  668.   
  669.   /* Find the range in file0 */
  670.   lowc = using[low_thread]->ranges[0][START];
  671.   highc = last_using[high_thread]->ranges[0][END];
  672.  
  673.   /* Find the ranges in the other files.
  674.      If using[x] is null, that means that the file to which that diff
  675.      refers is equivalent to file 0 over this range */
  676.   
  677.   if (using[0])
  678.     {
  679.       low1 = D_LOW_MAPLINE (using[0], FILE0, FILE1, lowc);
  680.       high1 = D_HIGH_MAPLINE (using[0], FILE0, FILE1, highc); 
  681.     }
  682.   else
  683.     {
  684.       low1 = D_HIGH_MAPLINE (last_diff, FILEC, FILE1, lowc);
  685.       high1 = D_HIGH_MAPLINE (last_diff, FILEC, FILE1, highc);
  686.     }
  687.  
  688.   /*
  689.    * Note that in the following, we use file 1 relative to the diff,
  690.    * and file 2 relative to the coresp lines struct.
  691.    */
  692.   if (using[1])
  693.     {
  694.       low2 = D_LOW_MAPLINE (using[1], FILE0, FILE1, lowc);
  695.       high2 = D_HIGH_MAPLINE (using[1], FILE0, FILE1, highc); 
  696.     }
  697.   else
  698.     {
  699.       low2 = D_HIGH_MAPLINE (last_diff, FILEC, FILE2, lowc);
  700.       high2 = D_HIGH_MAPLINE (last_diff, FILEC, FILE2, highc);
  701.     }
  702.  
  703.   /* Create a block with the appropriate sizes */
  704.   result = create_diff3_block (lowc, highc, low1, high1, low2, high2);
  705.  
  706.   /* Copy over all of the information for File 0.  Return with a zero
  707.      if any of the compares failed. */
  708.   for (ptr = using[0]; ptr; ptr = D_NEXT (ptr))
  709.     {
  710.       int result_offset = D_LOWLINE (ptr, FILE0) - lowc;
  711.       int copy_size
  712.     = D_HIGHLINE (ptr, FILE0) - D_LOWLINE (ptr, FILE0) + 1;
  713.       
  714.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE0),
  715.                 D_LENARRAY (ptr, FILE0),
  716.                 D_LINEARRAY (result, FILEC) + result_offset,
  717.                 D_LENARRAY (result, FILEC) + result_offset,
  718.                 copy_size))
  719.     return 0;
  720.     }
  721.  
  722.   for (ptr = using[1]; ptr; ptr = D_NEXT (ptr))
  723.     {
  724.       int result_offset = D_LOWLINE (ptr, FILEC) - lowc;
  725.       int copy_size
  726.     = D_HIGHLINE (ptr, FILEC) - D_LOWLINE (ptr, FILEC) + 1;
  727.       
  728.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE0),
  729.                 D_LENARRAY (ptr, FILE0),
  730.                 D_LINEARRAY (result, FILEC) + result_offset,
  731.                 D_LENARRAY (result, FILEC) + result_offset,
  732.                 copy_size))
  733.     return 0;
  734.     }
  735.  
  736.   /* Copy stuff for file 1.  First deal with anything that might be
  737.      before the first diff. */
  738.  
  739.   for (i = 0;
  740.        i + low1 < (using[0] ? D_LOWLINE (using[0], FILE1) : high1 + 1);
  741.        i++)
  742.     {
  743.       D_RELNUM (result, FILE1, i) = D_RELNUM (result, FILEC, i);
  744.       D_RELLEN (result, FILE1, i) = D_RELLEN (result, FILEC, i);
  745.     }
  746.   
  747.   for (ptr = using[0]; ptr; ptr = D_NEXT (ptr))
  748.     {
  749.       int result_offset = D_LOWLINE (ptr, FILE1) - low1;
  750.       int copy_size
  751.     = D_HIGHLINE (ptr, FILE1) - D_LOWLINE (ptr, FILE1) + 1;
  752.  
  753.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE1),
  754.                 D_LENARRAY (ptr, FILE1),
  755.                 D_LINEARRAY (result, FILE1) + result_offset,
  756.                 D_LENARRAY (result, FILE1) + result_offset,
  757.                 copy_size))
  758.     return 0;
  759.  
  760.       /* Catch the lines between here and the next diff */
  761.       current0line = D_HIGHLINE (ptr, FILE0) + 1 - lowc;
  762.       for (i = D_HIGHLINE (ptr, FILE1) + 1 - low1;
  763.        i < (D_NEXT (ptr) ?
  764.         D_HIGHLINE (D_NEXT (ptr), FILE1) :
  765.         high1 + 1) - low1;
  766.        i++)
  767.     {
  768.       D_RELNUM (result, FILE1, i)
  769.         = D_RELNUM (result, FILEC, current0line);
  770.       D_RELLEN (result, FILE1, i)
  771.         = D_RELLEN (result, FILEC, current0line++);
  772.     }
  773.     }
  774.  
  775.   /* Copy stuff for file 2.  First deal with anything that might be
  776.      before the first diff. */
  777.  
  778.   for (i = 0;
  779.        i + low2 < (using[1] ? D_LOWLINE (using[1], FILE1) : high2 + 1);
  780.        i++)
  781.     {
  782.       D_RELNUM (result, FILE2, i) = D_RELNUM (result, FILEC, i);
  783.       D_RELLEN (result, FILE2, i) = D_RELLEN (result, FILEC, i);
  784.     }
  785.   
  786.   for (ptr = using[1]; ptr; ptr = D_NEXT (ptr))
  787.     {
  788.       int result_offset = D_LOWLINE (ptr, FILE1) - low2;
  789.       int copy_size
  790.     = D_HIGHLINE (ptr, FILE1) - D_LOWLINE (ptr, FILE1) + 1;
  791.  
  792.       if (!copy_stringlist (D_LINEARRAY (ptr, FILE1),
  793.                 D_LENARRAY (ptr, FILE1),
  794.                 D_LINEARRAY (result, FILE2) + result_offset,
  795.                 D_LENARRAY (result, FILE2) + result_offset,
  796.                 copy_size))
  797.     return 0;
  798.  
  799.       /* Catch the lines between here and the next diff */
  800.       current0line = D_HIGHLINE (ptr, FILE0) + 1 - lowc;
  801.       for (i = D_HIGHLINE (ptr, FILE1) + 1 - low2;
  802.        i < (D_NEXT (ptr) ?
  803.         D_HIGHLINE (D_NEXT (ptr), FILE1) :
  804.         high2 + 1) - low2;
  805.        i++)
  806.     {
  807.       D_RELNUM (result, FILE2, i)
  808.         = D_RELNUM (result, FILEC, current0line);
  809.       D_RELLEN (result, FILE2, i)
  810.         = D_RELLEN (result, FILEC, current0line++);
  811.     }
  812.     }
  813.  
  814.   /* Set correspond */
  815.   if (!using[0])
  816.     D3_TYPE (result) = DIFF_3RD;
  817.   else if (!using[1])
  818.     D3_TYPE (result) = DIFF_2ND;
  819.   else
  820.     {
  821.       int nl1
  822.     = D_HIGHLINE (result, FILE1) - D_LOWLINE (result, FILE1) + 1;
  823.       int nl2
  824.     = D_HIGHLINE (result, FILE2) - D_LOWLINE (result, FILE2) + 1;
  825.  
  826.       if (nl1 != nl2
  827.       || !compare_line_list (D_LINEARRAY (result, FILE1),
  828.                  D_LENARRAY (result, FILE1),
  829.                  D_LINEARRAY (result, FILE2),
  830.                  D_LENARRAY (result, FILE2),
  831.                  nl1))
  832.     D3_TYPE (result) = DIFF_ALL;
  833.       else
  834.     D3_TYPE (result) = DIFF_1ST;
  835.     }
  836.   
  837.   return result;
  838. }
  839.  
  840. /*
  841.  * This routine copies pointers from a list of strings to a different list
  842.  * of strings.  If a spot in the second list is already filled, it
  843.  * makes sure that it is filled with the same string; if not it
  844.  * returns 0, the copy incomplete.
  845.  * Upon successful completion of the copy, it returns 1.
  846.  */
  847. int
  848. copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum)
  849. char *fromptrs[], *toptrs[];
  850. int *fromlengths, *tolengths;
  851. int copynum;
  852. {
  853.   register char
  854.     **f = fromptrs,
  855.     **t = toptrs;
  856.   register int
  857.     *fl = fromlengths,
  858.     *tl = tolengths;
  859.   
  860.   while (copynum--)
  861.     {
  862.       if (*t)
  863.     { if (*fl != *tl || bcmp (*f, *t, *fl)) return 0; }
  864.       else
  865.     { *t = *f ; *tl = *fl; }
  866.  
  867.       t++; f++; tl++; fl++;
  868.     }
  869.   return 1;
  870. }
  871.  
  872. /*
  873.  * Create a diff3_block, with ranges as specified in the arguments.
  874.  * Allocate the arrays for the various pointers (and zero them) based
  875.  * on the arguments passed.  Return the block as a result.
  876.  */
  877. struct diff3_block *
  878. create_diff3_block (low0, high0, low1, high1, low2, high2)
  879. register int low0, high0, low1, high1, low2, high2;
  880. {
  881.   struct diff3_block *result = ALLOCATE (1, struct diff3_block);
  882.   int numlines;
  883.  
  884.   D3_TYPE (result) = ERROR;
  885.  
  886.   /* Assign ranges */
  887.   D_LOWLINE (result, FILE0) = low0;
  888.   D_HIGHLINE (result, FILE0) = high0;
  889.   D_LOWLINE (result, FILE1) = low1;
  890.   D_HIGHLINE (result, FILE1) = high1;
  891.   D_LOWLINE (result, FILE2) = low2;
  892.   D_HIGHLINE (result, FILE2) = high2;
  893.  
  894.   /* Allocate and zero space */
  895.   numlines = D_NUMLINES (result, FILE0);
  896.   if (numlines)
  897.     {
  898.       D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *);
  899.       D_LENARRAY (result, FILE0) = ALLOCATE (numlines, int);
  900.       bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *)));
  901.       bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (int)));
  902.     }
  903.   else
  904.     {
  905.       D_LINEARRAY (result, FILE0) = (char **) 0;
  906.       D_LENARRAY (result, FILE0) = (int *) 0;
  907.     }
  908.  
  909.   numlines = D_NUMLINES (result, FILE1);
  910.   if (numlines)
  911.     {
  912.       D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *);
  913.       D_LENARRAY (result, FILE1) = ALLOCATE (numlines, int);
  914.       bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *)));
  915.       bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (int)));
  916.     }
  917.   else
  918.     {
  919.       D_LINEARRAY (result, FILE1) = (char **) 0;
  920.       D_LENARRAY (result, FILE1) = (int *) 0;
  921.     }
  922.  
  923.   numlines = D_NUMLINES (result, FILE2);
  924.   if (numlines)
  925.     {
  926.       D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *);
  927.       D_LENARRAY (result, FILE2) = ALLOCATE (numlines, int);
  928.       bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *)));
  929.       bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (int)));
  930.     }
  931.   else
  932.     {
  933.       D_LINEARRAY (result, FILE2) = (char **) 0;
  934.       D_LENARRAY (result, FILE2) = (int *) 0;
  935.     }
  936.  
  937.   /* Return */
  938.   return result;
  939. }
  940.  
  941. /*
  942.  * Compare two lists of lines of text.
  943.  * Return 1 if they are equivelent, 0 if not.
  944.  */
  945. int
  946. compare_line_list (list1, lengths1, list2, lengths2, nl)
  947. char *list1[], *list2[];
  948. int *lengths1, *lengths2;
  949. int nl;
  950. {
  951.   char
  952.     **l1 = list1,
  953.     **l2 = list2;
  954.   int
  955.     *lgths1 = lengths1,
  956.     *lgths2 = lengths2;
  957.   
  958.   while (nl--)
  959.     if (!*l1 || !*l2 || *lgths1 != *lgths2++
  960.     || bcmp (*l1++, *l2++, *lgths1++))
  961.       return 0;
  962.   return 1;
  963. }
  964.  
  965. /* 
  966.  * Routines to input and parse two way diffs.
  967.  */
  968.  
  969. /* extern char *environ; */        /* I hope this is here */
  970.  
  971. #define    DIFF_CHUNK_SIZE    10000
  972.  
  973. struct diff_block *
  974. process_diff (filea, fileb)
  975. char *filea, *fileb;
  976. {
  977.   char *diff_contents;
  978.   int diff_size;
  979.   char *scan_diff;
  980.   enum diff_type dt;
  981.   int i;
  982.   struct diff_block *block_list, *block_list_end, *bptr;
  983.  
  984.   diff_size = read_diff (filea, fileb, &diff_contents);
  985.   scan_diff = diff_contents;
  986.   bptr = block_list_end = block_list = (struct diff_block *) 0;
  987.  
  988.   while (scan_diff - diff_contents < diff_size)
  989.     {
  990.       bptr = ALLOCATE (1, struct diff_block);
  991.       bptr->lines[0] = bptr->lines[1] = (char **) 0;
  992.       bptr->lengths[0] = bptr->lengths[1] = (int *) 0;
  993.       
  994.       dt = process_diff_control (&scan_diff, bptr);
  995.       if (dt == ERROR) fatal ("Bad format in diff output");
  996.       if (*scan_diff != '\n') fatal ("Bad format in diff output");
  997.       scan_diff++;
  998.       
  999.       /* Force appropriate ranges to be null, if necessary */
  1000.       switch (dt)
  1001.     {
  1002.     case ADD:
  1003.       bptr->ranges[0][0]++;
  1004.       break;
  1005.     case DELETE:
  1006.       bptr->ranges[1][0]++;
  1007.       break;
  1008.     case CHANGE:
  1009.       break;
  1010.     default:
  1011.       fatal ("internal: Bad diff type in process_diff");
  1012.       break;
  1013.     }
  1014.       
  1015.       /* Allocate space for the pointers for the lines from filea, and
  1016.      parsel them out among these pointers */
  1017.       if (dt != ADD)
  1018.     {
  1019.       bptr->lines[0] = ALLOCATE ((bptr->ranges[0][END]
  1020.                       - bptr->ranges[0][START] + 1),
  1021.                      char *);
  1022.       bptr->lengths[0] = ALLOCATE ((bptr->ranges[0][END]
  1023.                     - bptr->ranges[0][START] + 1),
  1024.                        int);
  1025.       for (i = 0; i <= (bptr->ranges[0][END]
  1026.                 - bptr->ranges[0][START]); i++)
  1027.         scan_diff = scan_diff_line (scan_diff,
  1028.                     &(bptr->lines[0][i]),
  1029.                     &(bptr->lengths[0][i]),
  1030.                     diff_contents + diff_size,
  1031.                     '<');
  1032.     }
  1033.       
  1034.       /* Get past the seperator for changes */
  1035.       if (dt == CHANGE)
  1036.     {
  1037.       if (strncmp (scan_diff, "---\n", 4))
  1038.         fatal ("Bad diff format: bad change seperater");
  1039.       scan_diff += 4;
  1040.     }
  1041.       
  1042.       /* Allocate space for the pointers for the lines from fileb, and
  1043.      parsel them out among these pointers */
  1044.       if (dt != DELETE)
  1045.     {
  1046.       bptr->lines[1] = ALLOCATE ((bptr->ranges[1][END]
  1047.                       - bptr->ranges[1][START] + 1),
  1048.                      char *);
  1049.       bptr->lengths[1] = ALLOCATE ((bptr->ranges[1][END]
  1050.                     - bptr->ranges[1][START] + 1),
  1051.                        int);
  1052.       for (i = 0; i <= (bptr->ranges[1][END]
  1053.                 - bptr->ranges[1][START]); i++)
  1054.         scan_diff = scan_diff_line (scan_diff,
  1055.                     &(bptr->lines[1][i]),
  1056.                     &(bptr->lengths[1][i]),
  1057.                     diff_contents + diff_size,
  1058.                     '>');
  1059.     }
  1060.       
  1061.       /* Place this block on the blocklist */
  1062.       if (block_list_end)
  1063.     block_list_end->next = bptr;
  1064.       else
  1065.     block_list = bptr;
  1066.       
  1067.       block_list_end = bptr;
  1068.       
  1069.     }
  1070.  
  1071.   if (scan_diff - diff_contents != diff_size)
  1072.     fatal ("bad diff format; incomplete last line");
  1073.  
  1074.   return block_list;
  1075. }
  1076.  
  1077. /*
  1078.  * This routine will parse a normal format diff control string.  It
  1079.  * returns the type of the diff (ERROR if the format is bad).  All of
  1080.  * the other important information is filled into to the structure
  1081.  * pointed to by db, and the string pointer (whose location is passed
  1082.  * to this routine) is updated to point beyond the end of the string
  1083.  * parsed.  Note that only the ranges in the diff_block will be set by
  1084.  * this routine.
  1085.  *
  1086.  * If some specific pair of numbers has been reduced to a single
  1087.  * number, then both corresponding numbers in the diff block are set
  1088.  * to that number.  In general these numbers are interpetted as ranges
  1089.  * inclusive, unless being used by the ADD or DELETE commands.  It is
  1090.  * assumed that these will be special cased in a superior routine.  
  1091.  */
  1092.  
  1093. enum diff_type
  1094. process_diff_control (string, db)
  1095. char **string;
  1096. struct diff_block *db;
  1097. {
  1098.   char *s = *string;
  1099.   int done = 0;
  1100.   int holdnum;
  1101.   enum diff_type type;
  1102.  
  1103. /* These macros are defined here because they can use variables
  1104.    defined in this function.  Don't try this at home kids, we're
  1105.    trained professionals!
  1106.  
  1107.    Also note that SKIPWHITE only recognizes tabs and spaces, and
  1108.    that READNUM can only read positive, integral numbers */
  1109.  
  1110. #define    SKIPWHITE(s)    { while (*s == ' ' || *s == '\t') s++; }
  1111. #define    READNUM(s, num)    \
  1112.     { if (!isdigit (*s)) return ERROR; holdnum = 0;    \
  1113.       do { holdnum = (*s++ - '0' + holdnum * 10); }    \
  1114.       while (isdigit (*s)); (num) = holdnum; }
  1115.  
  1116.   /* Read first set of digits */
  1117.   SKIPWHITE (s);
  1118.   READNUM (s, db->ranges[0][START]);
  1119.  
  1120.   /* Was that the only digit? */
  1121.   SKIPWHITE(s);
  1122.   if (*s == ',')
  1123.     {
  1124.       /* Get the next digit */
  1125.       s++;
  1126.       READNUM (s, db->ranges[0][END]);
  1127.     }
  1128.   else
  1129.     db->ranges[0][END] = db->ranges[0][START];
  1130.  
  1131.   /* Get the letter */
  1132.   SKIPWHITE (s);
  1133.   switch (*s)
  1134.     {
  1135.     case 'a':
  1136.       type = ADD;
  1137.       break;
  1138.     case 'c':
  1139.       type = CHANGE;
  1140.       break;
  1141.     case 'd':
  1142.       type = DELETE;
  1143.       break;
  1144.     default:
  1145.       return ERROR;            /* Bad format */
  1146.     }
  1147.   s++;                /* Past letter */
  1148.   
  1149.   /* Read second set of digits */
  1150.   SKIPWHITE (s);
  1151.   READNUM (s, db->ranges[1][START]);
  1152.  
  1153.   /* Was that the only digit? */
  1154.   SKIPWHITE(s);
  1155.   if (*s == ',')
  1156.     {
  1157.       /* Get the next digit */
  1158.       s++;
  1159.       READNUM (s, db->ranges[1][END]);
  1160.       SKIPWHITE (s);        /* To move to end */
  1161.     }
  1162.   else
  1163.     db->ranges[1][END] = db->ranges[1][START];
  1164.  
  1165.   *string = s;
  1166.   return type;
  1167. }
  1168.  
  1169. int
  1170. read_diff (filea, fileb, output_placement)
  1171. char *filea, *fileb;
  1172. char **output_placement;
  1173. {
  1174.   char *argv[4];
  1175.   char *diff_result;
  1176.   long current_chunk_size;
  1177.   int bytes;
  1178.   char *buffer_ptr;
  1179.   int total;
  1180.   int fds[2];
  1181. #ifdef MSDOS
  1182.   char *tmpnam(), *tname;
  1183.   char tbuf[200];
  1184.   tname = tmpnam(NULL);
  1185. #endif
  1186.  
  1187.   argv[0] = diff_program;
  1188.   argv[1] = filea;
  1189.   argv[2] = fileb;
  1190.   argv[3] = (char *) 0;
  1191.  
  1192. #ifndef MSDOS
  1193.   pipe (fds);
  1194.  
  1195.   if (!fork ())
  1196.     {
  1197.       /* Child */
  1198.       dup2 (fds[1], 1);        /* Make stdout the pipe to the parent */
  1199.       /* Leave stdin alone; the diff may need it */
  1200.       execve (diff_program, argv, environ);
  1201.       perror_with_exit ("Exec failed");
  1202.     }
  1203.  
  1204.   close (fds[1]);        /* Prevent erroneous lack of EOF */
  1205. #else
  1206.     strcpy(tbuf,diff_program);
  1207.     strcat(tbuf," ");
  1208.     strcat(tbuf, argv[1]);
  1209.     strcat(tbuf," ");
  1210.     strcat(tbuf, argv[2]);
  1211.     strcat(tbuf," >");
  1212.     strcat(tbuf, tname);
  1213.     system(tbuf);
  1214.     fds[0] = open(tname, O_RDONLY);
  1215.  
  1216. #endif
  1217.  
  1218.   current_chunk_size = DIFF_CHUNK_SIZE;
  1219.   diff_result = (char *) xmalloc (current_chunk_size);
  1220.   total = 0;
  1221.   do {
  1222.     bytes = myread (fds[0],
  1223.             diff_result + total,
  1224.             current_chunk_size - total);
  1225.     total += bytes;
  1226.     if (total == current_chunk_size)
  1227.       diff_result = (char *) xrealloc (diff_result, (current_chunk_size *= 2));
  1228.   } while (bytes);
  1229.  
  1230.   *output_placement = diff_result;
  1231.  
  1232.  
  1233.   return total;
  1234. }
  1235.  
  1236.  
  1237.  
  1238. /*
  1239.  * Scan a regular diff line (consisting of > or <, followed by a
  1240.  * space, followed by text (including nulls) up to a newline.
  1241.  *
  1242.  * This next routine began life as a macro and many parameters in it
  1243.  * are used as call-by-reference values.
  1244.  */
  1245. char *
  1246. scan_diff_line (scan_ptr, set_start, set_length, limit, firstchar)
  1247. char *scan_ptr, **set_start;
  1248. int *set_length;
  1249. char *limit;
  1250.      char firstchar;
  1251. {
  1252.   char *line_ptr = scan_ptr + 2;
  1253.  
  1254.   if (!(scan_ptr[0] == (firstchar)
  1255.     && scan_ptr[1] == ' '))
  1256.     fatal ("Bad diff format; incorrect leading line chars");
  1257.  
  1258.   *set_start = line_ptr;
  1259.   while (*line_ptr != '\n') line_ptr++;
  1260.   
  1261.   if (line_ptr >= limit)
  1262.     fatal ("Bad diff format; overflow in parse");
  1263.  
  1264.   /* Don't include newline, but do return the beginning of the
  1265.      next line */
  1266.   *set_length = line_ptr - *set_start;
  1267.  
  1268.   return line_ptr + 1;
  1269. }
  1270.  
  1271. /*
  1272.  * This routine outputs a three way diff passed as a list of
  1273.  * diff3_block's.
  1274.  * The argument MAPPING is indexed by external file number (in the
  1275.  * argument list) and contains the internal file number (from the
  1276.  * diff passed).  This is important because the user expects his
  1277.  * outputs in terms of the argument list number, and the diff passed
  1278.  * may have been done slightly differently (if the first argument in
  1279.  * the argument list was the standard input, for example).
  1280.  */
  1281. void
  1282. output_diff3 (outputfile, diff, mapping)
  1283. FILE *outputfile;
  1284. struct diff3_block *diff;
  1285. int mapping[3];
  1286. {
  1287.   int rev_mapping[3];
  1288.   static int eliminate[3] = { 1, 0, 0};
  1289.   int i, j;
  1290.   int oddoneout;
  1291.   char *cp;
  1292.   struct diff3_block *ptr;
  1293.   int line;
  1294.   int dontprint;
  1295.   static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
  1296.  
  1297.   for (i = 0; i < 3; i++)
  1298.     rev_mapping [mapping[i]] = i;
  1299.  
  1300.   for (ptr = diff; ptr; ptr = D_NEXT (ptr))
  1301.     {
  1302.       char x[2];
  1303.  
  1304.       switch (ptr->correspond)
  1305.     {
  1306.     case DIFF_ALL:
  1307.       x[0] = '\0';
  1308.       dontprint = 3;    /* Print them all */
  1309.       oddoneout = 3;    /* Nobody's odder than anyone else */
  1310.       break;
  1311.     case DIFF_1ST:
  1312.     case DIFF_2ND:
  1313.     case DIFF_3RD:
  1314.       oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST];
  1315.         
  1316.       x[0] = oddoneout + '1';
  1317.       x[1] = '\0';
  1318.       dontprint = eliminate [oddoneout];
  1319.       break;
  1320.     default:
  1321.       fatal ("internal: Bad diff type passed to output");
  1322.     }
  1323.       fprintf (outputfile, "====%s\n", x);
  1324.  
  1325.       /* Go 0, 2, 1 if the first and third outputs are equivalent. */
  1326.       for (i = 0; i < 3;
  1327.        i = (oddoneout == 1 ? skew_increment[i] : i + 1))
  1328.     {
  1329.       int realfile = mapping[i];
  1330.       int
  1331.         lowt = D_LOWLINE (ptr, realfile),
  1332.         hight = D_HIGHLINE (ptr, realfile);
  1333.       
  1334.       fprintf (outputfile, "%d:", i + 1);
  1335.       switch (lowt - hight)
  1336.         {
  1337.         case 1:
  1338.           fprintf (outputfile, "%da\n", lowt - 1);
  1339.           break;
  1340.         case 0:
  1341.           fprintf (outputfile, "%dc\n", lowt);
  1342.           break;
  1343.         default:
  1344.           fprintf (outputfile, "%d,%dc\n", lowt, hight);
  1345.           break;
  1346.         }
  1347.  
  1348.       if (i == dontprint) continue;
  1349.  
  1350.       for (line = 0; line < hight - lowt + 1; line++)
  1351.         {
  1352.           fprintf (outputfile, "  ");
  1353.           for (cp = D_RELNUM (ptr, realfile, line);
  1354.            cp < (D_RELNUM (ptr, realfile, line)
  1355.              + D_RELLEN (ptr, realfile, line));
  1356.            cp++)
  1357.         putc (*cp, outputfile);
  1358.           putc ('\n', outputfile);
  1359.         }
  1360.     }
  1361.     }
  1362. }
  1363.  
  1364. /*
  1365.  * This routine outputs a diff3 set of blocks as an ed script.  This
  1366.  * script applies the changes between file's 2 & 3 to file 1.  It
  1367.  * takes the precise format of the ed script to be output from global
  1368.  * variables set during options processing.  Note that it does
  1369.  * destructive things to the set of diff3 blocks it is passed; it
  1370.  * reverses their order (this gets around the problems involved with
  1371.  * changing line numbers in an ed script).
  1372.  *
  1373.  * Note that this routine has the same problem of mapping as the last
  1374.  * one did; the variable MAPPING maps from file number according to
  1375.  * the argument list to file number according to the diff passed.  All
  1376.  * files listed below are in terms of the argument list.
  1377.  *
  1378.  * Also, occaisionally this routine needs the real names of the files
  1379.  * on which it works.  Thus file0, file1, and file2 are the filenames
  1380.  * passed on the command line.
  1381.  *
  1382.  * See options.h for documentation on the global variables which this
  1383.  * routine pays attention to.
  1384.  */
  1385. void
  1386. output_diff3_edscript (outputfile, diff, mapping, file0, file1, file2)
  1387. FILE *outputfile;
  1388. struct diff3_block *diff;
  1389. int mapping[3];
  1390. char *file0, *file1, *file2;
  1391. {
  1392.   int rev_mapping[3];
  1393.   int i;
  1394.   int leading_dot;
  1395.   struct diff3_block *newblock, *thisblock;
  1396.   char *cp;
  1397.  
  1398.   leading_dot = 0;
  1399.  
  1400.   for (i = 0; i < 3; i++)
  1401.     rev_mapping [mapping [i]] = i;
  1402.  
  1403.   newblock = reverse_diff3_blocklist (diff);
  1404.  
  1405.   for (thisblock = newblock; thisblock; thisblock = thisblock->next)
  1406.     {
  1407.       /* Must do mapping correctly.  */
  1408.       enum diff_type type
  1409.     = ((thisblock->correspond == DIFF_ALL) ?
  1410.        DIFF_ALL :
  1411.        ((enum diff_type)
  1412.         (((int) DIFF_1ST)
  1413.          + rev_mapping [(int) thisblock->correspond - (int) DIFF_1ST])));
  1414.  
  1415.       /* If we aren't supposed to do this output block, skip it */
  1416.       if (type == DIFF_2ND || type == DIFF_1ST
  1417.       || (type == DIFF_3RD && dont_write_simple)
  1418.       || (type == DIFF_ALL && dont_write_overlap))
  1419.     continue;
  1420.  
  1421.       if (flagging && type == DIFF_ALL)
  1422.     /* Do special flagging */
  1423.     {
  1424.  
  1425.       /* Put in lines from FILE2 with bracket */
  1426.       fprintf (outputfile, "%da\n",
  1427.            D_HIGHLINE (thisblock, mapping [FILE0]));
  1428.       fprintf (outputfile, "=======\n");
  1429.       for (i = 0;
  1430.            i < D_NUMLINES (thisblock, mapping [FILE2]);
  1431.            i++)
  1432.         {
  1433.           if (D_RELNUM (thisblock, mapping[FILE2], i)[0] == '.')
  1434.         { leading_dot = 1; fprintf(outputfile, "."); }
  1435.           for (cp = D_RELNUM (thisblock, mapping [FILE2], i);
  1436.            cp < (D_RELNUM (thisblock, mapping [FILE2], i)
  1437.              + D_RELLEN (thisblock, mapping [FILE2], i));
  1438.            cp++)
  1439.         putc (*cp, outputfile);
  1440.           putc ('\n', outputfile);
  1441.         }
  1442.       fprintf (outputfile, ">>>>>>> %s\n.\n", file2);
  1443.  
  1444.       /* Add in code to take care of leading dots, if necc. */
  1445.       if (leading_dot)
  1446.         {
  1447.           fprintf (outputfile, "%d,%ds/^\\.\\./\\./\n",
  1448.                D_HIGHLINE (thisblock, mapping [FILE0]) + 1,
  1449.                (D_HIGHLINE (thisblock, mapping [FILE0])
  1450.             + D_NUMLINES (thisblock, mapping [FILE2])));
  1451.           leading_dot = 0;
  1452.         }
  1453.  
  1454.       /* Put in code to do initial bracket of lines from FILE0  */
  1455.       fprintf (outputfile, "%da\n<<<<<<< %s\n.\n",
  1456.            D_LOWLINE (thisblock, mapping[FILE0]) - 1,
  1457.            file0);
  1458.     }
  1459.       else if (D_NUMLINES (thisblock, mapping [FILE2]) == 0)
  1460.     /* Write out a delete */
  1461.     {
  1462.       if (D_NUMLINES (thisblock, mapping [FILE0]) == 1)
  1463.         fprintf (outputfile, "%dd\n",
  1464.              D_LOWLINE (thisblock, mapping [FILE0]));
  1465.       else
  1466.         fprintf (outputfile, "%d,%dd\n",
  1467.              D_LOWLINE (thisblock, mapping [FILE0]),
  1468.              D_HIGHLINE (thisblock, mapping [FILE0]));
  1469.     }
  1470.       else
  1471.     /* Write out an add or change */
  1472.     {
  1473.       switch (D_NUMLINES (thisblock, mapping [FILE0]))
  1474.         {
  1475.         case 0:
  1476.           fprintf (outputfile, "%da\n",
  1477.                D_HIGHLINE (thisblock, mapping [FILE0]));
  1478.           break;
  1479.         case 1:
  1480.           fprintf (outputfile, "%dc\n",
  1481.                D_HIGHLINE (thisblock, mapping [FILE0]));
  1482.           break;
  1483.         default:
  1484.           fprintf (outputfile, "%d,%dc\n",
  1485.                D_LOWLINE (thisblock, mapping [FILE0]),
  1486.                D_HIGHLINE (thisblock, mapping [FILE0]));
  1487.           break;
  1488.         }
  1489.       for (i = 0;
  1490.            i < D_NUMLINES (thisblock, mapping [FILE2]);
  1491.            i++)
  1492.         {
  1493.           if (D_RELNUM (thisblock, mapping [FILE2], i)[0] == '.')
  1494.         { leading_dot = 1; fprintf (outputfile, "."); }
  1495.           for (cp = D_RELNUM (thisblock, mapping [FILE2], i);
  1496.            cp < (D_RELNUM (thisblock, mapping [FILE2], i)
  1497.              + D_RELLEN (thisblock, mapping [FILE2], i));
  1498.            cp++)
  1499.         putc (*cp, outputfile);
  1500.           putc ('\n', outputfile);
  1501.         }
  1502.       fprintf (outputfile, ".\n");
  1503.       
  1504.       /* Add in code to take care of leading dots, if necc. */
  1505.       if (leading_dot)
  1506.         {
  1507.           fprintf (outputfile, "%d,%ds/^\\.\\./\\./\n",
  1508.                D_HIGHLINE (thisblock, mapping [FILE0]) + 1,
  1509.                (D_HIGHLINE (thisblock, mapping [FILE0])
  1510.             + D_NUMLINES (thisblock, mapping [FILE2])));
  1511.           leading_dot = 0;
  1512.         }
  1513.     }
  1514.     }
  1515.   if (finalwrite) fprintf (outputfile, "w\nq\n");
  1516. }
  1517.  
  1518. /*
  1519.  * Reverse the order of the list of diff3 blocks.
  1520.  */
  1521. struct diff3_block *
  1522. reverse_diff3_blocklist (diff)
  1523. struct diff3_block *diff;
  1524. {
  1525.   register struct diff3_block *tmp, *next, *prev;
  1526.  
  1527.   for (tmp = diff, prev = (struct diff3_block *) 0;
  1528.        tmp; tmp = next)
  1529.     {
  1530.       next = tmp->next;
  1531.       tmp->next = prev;
  1532.       prev = tmp;
  1533.     }
  1534.   
  1535.   return prev;
  1536. }
  1537.  
  1538. int
  1539. myread (fd, ptr, size)
  1540. int fd, size;
  1541. char *ptr;
  1542. {
  1543.   int result = read (fd, ptr, size);
  1544.   if (result < 0)
  1545.     perror_with_exit ("Read failed");
  1546.   return result;
  1547. }
  1548.  
  1549. void *
  1550. xmalloc (size)
  1551. int size;
  1552. {
  1553.   void *result = (void *) malloc (size);
  1554.   if (!result)
  1555.     fatal ("Malloc failed");
  1556.   return result;
  1557. }
  1558.  
  1559. void *
  1560. xrealloc (ptr, size)
  1561. void *ptr;
  1562. int size;
  1563. {
  1564.   void *result = (void *) realloc (ptr, size);
  1565.   if (!result)
  1566.     fatal ("Malloc failed");
  1567.   return result;
  1568. }
  1569.  
  1570. void
  1571. fatal (string)
  1572. char *string;
  1573. {
  1574.   char *message = (char *) alloca (strlen (string)
  1575.                    + strlen (argv0)
  1576.                    + 1);
  1577.  
  1578.   strcpy (message, argv0);
  1579.   strcat (message, ": ");
  1580.   strcat (message, string);
  1581.   printf (message);
  1582.   exit (1);
  1583. }
  1584.  
  1585. perror_with_exit (string)
  1586. char *string;
  1587. {
  1588.   perror (string);
  1589.   exit (1);
  1590. }
  1591.